iT邦幫忙

2021 iThome 鐵人賽

DAY 24
0

希爾排序法(Shell Sort)是插入排序(Insertion Sort)的改良版。可減少插入排序的資料搬移次數,加入了間距(Gap)的概念將資料分成多個小區塊,再將不同區塊資料進行插入排序,每一回合Gap會漸漸減少,最後一回Gap會是1。

操作流程:

  • 由大到小制定數個間距(Gap),最後一次的Gap一定要是1
  • 將資料依制定的間距(Gap)分組
  • 每組進行插入排序
  • 重複上述步驟,不斷減少Gap,直到最後一次Gap是1完成為止。

間距(Gap)的選擇:

發明人D.L Shell原先的Gap選擇為:N/2、N/4、...1(反覆除以2)

間距Gap的選擇有非常多種,這邊用最初發明人為例,其他選擇可自行google研究。


下面利用60 80 20 30 40 70 50 10由小到大排序。
https://ithelp.ithome.com.tw/upload/images/20211005/20121027nnuj7cMmXb.jpg


時間複雜度會因選用的GAP有所不同,但因為是插入排序改良版,幾乎所有狀況都能比O(n²)來得快

插入排序法的介紹可以參考此篇


JavaScript

let data = [8, 6, 10, 5, 3, 9, 2, 7, 4, 1]

function ShellSort(data) {
  let i, j, tmp;
  let gap = parseInt(data.length / 2);
  
  for (gap; gap > 0; gap = parseInt(gap / 2)) {
    //開始插入排序法 
    for (i = gap; i < data.length; i++) {
      tmp = data[i];
      for (j = i; j >= gap && tmp < data[j - gap]; j -= gap) {
        data[j] = data[j - gap];
      }
      data[j] = tmp;
    }
  }
  return data
}

console.log(ShellSort(data))//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Python

#Shell Sort
data = [89, 34, 23, 78, 67, 100, 66, 29, 79, 55, 78, 88, 92, 96, 96, 23]

def ShellSort(data):
    n = len(data)
    gap = n // 2 
    while gap > 0: 
        for i in range(gap,n): 
            temp = data[i] 
            j = i 
            while  j >= gap and data[j-gap] > temp: 
                data[j] = data[j-gap] 
                j = j - gap 
            data[j] = temp 
        gap = gap // 2
    return data
        
print(ShellSort(data))
#[23, 23, 29, 34, 55, 66, 67, 78, 78, 79, 88, 89, 92, 96, 96, 100]

上一篇
【Day23】[演算法]-插入排序法Insertion Sort
下一篇
【Day25】[演算法]-合併排序法Merge Sort
系列文
資料結構與演算法,使用JavaScript與Python35
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言